package com.ict.ycwl.pathcalculate.service.Impl;

import com.baomidou.mybatisplus.core.conditions.query.QueryWrapper;
import com.fasterxml.jackson.databind.JsonNode;
import com.fasterxml.jackson.databind.ObjectMapper;
import com.ict.ycwl.pathcalculate.common.exception.CarNumberException;
import com.ict.ycwl.pathcalculate.mapper.*;
import com.ict.ycwl.pathcalculate.pojo.*;
import com.ict.ycwl.pathcalculate.service.CalculateService;
import com.ict.ycwl.pathcalculate.utils.AccumulationUtils;
import com.ict.ycwl.pathcalculate.utils.ConvexHull;
import org.apache.commons.math3.ml.clustering.CentroidCluster;
import org.apache.commons.math3.ml.clustering.KMeansPlusPlusClusterer;
import org.apache.commons.math3.ml.distance.EuclideanDistance;
import org.apache.commons.math3.random.MersenneTwister;
import org.apache.commons.math3.random.RandomGenerator;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.stereotype.Service;

import javax.annotation.Resource;
import java.io.IOException;
import java.math.BigDecimal;
import java.net.HttpURLConnection;
import java.net.URL;
import java.time.LocalDateTime;
import java.time.format.DateTimeFormatter;
import java.util.*;

/**
 * @author yuhuaame
 */
@Service
public class CalculateServiceImpl implements CalculateService {

    @Autowired
    private AccumulationMapper accumulationMapper;
    @Autowired
    private PointDistanceMapper pointDistanceMapper;
    @Autowired
    private TransitDepotMapper transitDepotMapper;
    @Autowired
    private StoreMapper storeMapper;
    @Autowired
    private GearMapper gearMapper;
    @Autowired
    private CarMapper carMapper;
    @Resource
    private AccumulationUtils accumulationUtils;
    @Autowired
    private RouteMapper routeMapper;

    @Override
    public List<CentroidCluster<DoublePoint>> assignNumberOfCluster(int assignNumber, List<LngAndLat> lngAndLats) {
//        List<LngAndLat> lngAndLats = pathAccumulationMapper.selectCoordinates();

        //过滤空值并获取经纬度信息，将经纬度信息存到lngLatMatrix中
        ArrayList<DoublePoint> lngLatMatrix = new ArrayList<>();

        for (LngAndLat ll : lngAndLats) {
            double[] doubles = {ll.getLongitude(), ll.getLatitude()};
            DoublePoint dp = new DoublePoint(doubles);
            lngLatMatrix.add(dp);
        }

        List<CentroidCluster<DoublePoint>> bestClusters = myKmeans(assignNumber, 30, 0, lngLatMatrix);
        return bestClusters;
    }

    @Override
    public List<ResultRoute> calculateAll(String apiKey) throws Exception {
//        //获取全部聚集区
//        QueryWrapper<Accumulation> queryWrapper = new QueryWrapper<>();
//        queryWrapper.eq("is_delete", 0);
//        List<Accumulation> accumulations = accumulationMapper.selectList(queryWrapper);
        accumulationUtils.updateAccumulationToDepot();

        //获取所有启用的中转场
        QueryWrapper<TransitDepot> queryWrapper1 = new QueryWrapper<>();
        queryWrapper1.eq("status", 1);
        List<TransitDepot> transitDepots = transitDepotMapper.selectList(queryWrapper1);

//        // 将每个聚集区划分到最近的中转站
//        for (Accumulation accumulation : accumulations) {
//            double[] d1 = new double[]{accumulation.getLongitude(), accumulation.getLatitude()};
//            double distance = Double.MAX_VALUE;
//
//            int flag = 0;
//            for (int j = 0; j < transitDepots.size(); j++) {
//                TransitDepot transitDepot = transitDepots.get(j);
//                double[] d2 = new double[]{Double.parseDouble(transitDepot.getLongitude()), Double.parseDouble(transitDepot.getLatitude())};
//                double v = calculateEuclideanDistance(d1, d2);
//                if (v < distance) {
//                    distance = v;
//                    flag = j;
//                }
//            }
//
//            TransitDepot transitDepot = transitDepots.get(flag);
//
//            UpdateWrapper<Accumulation> updateWrapper = new UpdateWrapper<>();
//            updateWrapper.eq("accumulation_id", accumulation.getAccumulationId()).eq("is_delete", 0).set("transit_depot_id", transitDepot.getTransitDepotId());
//            accumulationMapper.update(null, updateWrapper);
//        }

//        //计算之前先将所有的路线软删除
//        UpdateWrapper<Route> updateWrapper = new UpdateWrapper<>();
//        updateWrapper.eq("is_delete", 0).set("is_delete", 1);
//        routeMapper.update(null, updateWrapper);

        //计算每个中转站的路线，并存储到数据库
        List<ResultRoute> routeResult = new ArrayList<>();
        for (TransitDepot transitDepot : transitDepots) {
            Long transitDepotId = transitDepot.getTransitDepotId();
            Long areaId = transitDepot.getAreaId();
            String transitDepotName = transitDepot.getTransitDepotName();

            //获取当前中转站所有的车
            QueryWrapper<Car> carQueryWrapper = new QueryWrapper<>();
            carQueryWrapper.eq("transit_depot_id", transitDepotId).eq("status", "1");
            List<Car> cars = carMapper.selectList(carQueryWrapper);

            QueryWrapper<Accumulation> queryWrapper2 = new QueryWrapper<>();
            queryWrapper2.eq("transit_depot_id", transitDepotId).eq("is_delete", 0);
            List<Accumulation> accumulations1 = accumulationMapper.selectList(queryWrapper2);

            List<LngAndLat> lngAndLats = new ArrayList<>();
            for (Accumulation a : accumulations1) {
                lngAndLats.add(new LngAndLat(a.getLongitude(), a.getLatitude()));
            }

            //进行计算并处理返回的结果
            Map<List<String>, Double> result = new LinkedHashMap<>();
            if (transitDepot.getTransitDepotName().contains("马市")) {
                result = calculate(30, lngAndLats, transitDepotId, new double[]{Double.parseDouble(transitDepot.getLongitude()), Double.parseDouble(transitDepot.getLatitude())}, apiKey);
            } else if (transitDepot.getTransitDepotName().contains("坪石")) {
                result = calculate(25, lngAndLats, transitDepotId, new double[]{Double.parseDouble(transitDepot.getLongitude()), Double.parseDouble(transitDepot.getLatitude())}, apiKey);
            } else if (transitDepot.getTransitDepotName().contains("物流配送中心")) {
                result = calculate(45, lngAndLats, transitDepotId, new double[]{Double.parseDouble(transitDepot.getLongitude()), Double.parseDouble(transitDepot.getLatitude())}, apiKey);
            } else if (transitDepot.getTransitDepotName().contains("翁源")) {
                result = calculate(15, lngAndLats, transitDepotId, new double[]{Double.parseDouble(transitDepot.getLongitude()), Double.parseDouble(transitDepot.getLatitude())}, apiKey);
            } else {
                result = calculate(10, lngAndLats, transitDepotId, new double[]{Double.parseDouble(transitDepot.getLongitude()), Double.parseDouble(transitDepot.getLatitude())}, apiKey);
            }

            Set<Map.Entry<List<String>, Double>> entries = result.entrySet();
            List<String> paths = new ArrayList<>();

            double distance = 0;
            //count和k用于对路线进行命名
            int count = 1;
            int k = 0;

            for (Map.Entry<List<String>, Double> m : entries) {
                double cargoWeight = 0;
                paths = m.getKey();
                distance = m.getValue();

                //将每一条路线做一下格式转换，然后存到数据库
                StringBuilder stringBuilder = new StringBuilder();
                for (int j = 0; j < paths.size(); j++) {
                    String path = paths.get(j);

                    if (j == paths.size() - 1) {
                        stringBuilder.append(path);
                    } else {
                        stringBuilder.append(path);
                        stringBuilder.append(";");
                    }
                }

                //遍历这条路径，计算出载货量（起点和终点都是中转站）
                List<LngAndLat> polyLine = new ArrayList<>();
                String[] split = stringBuilder.toString().split(";");
                String[] origin = split[0].split(",");
                polyLine.add(new LngAndLat(Double.parseDouble(origin[0]), Double.parseDouble(origin[1])));
                for (int i1 = 1; i1 < split.length - 1; i1++) {
                    String[] split1 = split[i1].split(",");

                    QueryWrapper<Store> storeQueryWrapper = new QueryWrapper<>();
                    try {
                        storeQueryWrapper.eq("longitude", split1[0]).eq("latitude", split1[1]);
                    } catch (ArrayIndexOutOfBoundsException a) {
                        continue;
                    }
                    Store store = storeMapper.selectList(storeQueryWrapper).get(0);
                    if (store == null) {
                        continue;
                    }

                    if (store.getGear() == null) {
                        continue;
                    }
                    QueryWrapper<Gear> gearQueryWrapper = new QueryWrapper<>();
                    gearQueryWrapper.eq("gear_name", store.getGear());
                    Gear gear = gearMapper.selectOne(gearQueryWrapper);

                    cargoWeight += Double.parseDouble(gear.getCargoWeight());

                    polyLine.add(new LngAndLat(Double.parseDouble(split1[0]), Double.parseDouble(split1[1])));
                }
                polyLine.add(new LngAndLat(Double.parseDouble(origin[0]), Double.parseDouble(origin[1])));
                //并计算除去中转站的凸包
                LngAndLat[] clist = new LngAndLat[polyLine.size() - 2];
                for (int i = 1; i < polyLine.size() - 1; i++) {
                    int j = i - 1;
                    clist[j] = polyLine.get(i);
                }
                List<LngAndLat> convex = null;
                if (polyLine.size() <= 5) {
                    convex = polyLine;
                    convex.remove(convex.size() - 1);
                    convex.remove(0);
                } else {
                    convex = ConvexHull.convexHull(clist);
                }
                convex.add(convex.get(0));

                //遍历这条路径，计算出载货量（起点和终点不再是中转站）
//                List<LngAndLat> polyLine = new ArrayList<>();
//                LngAndLat[] list = new LngAndLat[polyLine.size()];
//                String[] split = stringBuilder.toString().split(";");
//                for (int i1 = 1; i1 < split.length - 1; i1++) {
//                    String[] split1 = split[i1].split(",");
//
//                    QueryWrapper<Store> storeQueryWrapper = new QueryWrapper<>();
//                    try {
//                        storeQueryWrapper.eq("longitude", split1[0]).eq("latitude", split1[1]);
//                    } catch (ArrayIndexOutOfBoundsException a) {
//                        continue;
//                    }
//                    Store store = new Store();
//                    try {
//                        store = storeMapper.selectList(storeQueryWrapper).get(0);
//                    } catch (IndexOutOfBoundsException a) {
//                        throw new IllegalArgumentException(String.format(split1[0], split1[1]));
//                    }
//                    if (store == null) {
//                        continue;
//                    }
//
//                    if (store.getGear() == null) {
//                        continue;
//                    }
//                    QueryWrapper<Gear> gearQueryWrapper = new QueryWrapper<>();
//                    gearQueryWrapper.eq("gear_name", store.getGear());
//                    Gear gear = gearMapper.selectOne(gearQueryWrapper);
//
//                    cargoWeight += Double.parseDouble(gear.getCargoWeight());
//
//                    polyLine.add(new LngAndLat(Double.parseDouble(split1[0]), Double.parseDouble(split1[1])));
//                }
//                for (int i = 0; i < polyLine.size(); i++) {
//                    list[i] = polyLine.get(i);
//                }
//                polyLine = ConvexHull.convexHull(list);
//                polyLine.add(polyLine.get(0));

//                Route route = new Route();
//                route.setPolyline(stringBuilder.toString());
//                route.setTransitDepotId(transitDepotId);
//                route.setRouteName(transitDepot.getTransitDepotName() + i);
//                route.setDistance(String.valueOf(distance));
//                route.setCargoWeight(String.valueOf(cargoWeight));
//                routeMapper.insert(route);
//                routeResult.add(route);
                String licensePlateNumber = null;
                try {
                    licensePlateNumber = cars.get(k).getLicensePlateNumber();
                } catch (IndexOutOfBoundsException e) {
                    throw new CarNumberException("车辆数不足，无法继续计算");
                }
                String day = null;
                switch (count) {
                    case 1:
                        day = "星期一";
                        break;
                    case 2:
                        day = "星期二";
                        break;
                    case 3:
                        day = "星期三";
                        break;
                    case 4:
                        day = "星期四";
                        break;
                    case 5:
                        day = "星期五";
                        break;
                }
                // 获取当前时间
                LocalDateTime currentTime = LocalDateTime.now();
                // 定义日期时间格式
                DateTimeFormatter formatter = DateTimeFormatter.ofPattern("yyyy.MM.dd");
                // 格式化当前时间
                String formattedTime = currentTime.format(formatter);

                ResultRoute resultRoute = new ResultRoute();
                resultRoute.setPolyline(polyLine);
                resultRoute.setTransitDepotId(transitDepotId);
                resultRoute.setRouteName(transitDepotName + "-" + licensePlateNumber + "-" + day + "-" + formattedTime);
                resultRoute.setDistance(String.format("%.2f", distance));
                resultRoute.setCargoWeight(String.format("%.2f", cargoWeight));
                resultRoute.setAreaId(areaId);
                if (Double.isInfinite(distance)) {
                    distance = Double.MAX_VALUE;
                }
//                resultRoute.setWorkTime(BigDecimal.valueOf(Double.parseDouble(String.format("%.2f", distance / 36))));
                resultRoute.setConvex(convex);
                routeResult.add(resultRoute);

                //对命名的星期几进行操作
                if (++count == 6) {
                    count = 1;
                    k++;
                }
            }
        }


//        QueryWrapper<Route> routeQueryWrapper = new QueryWrapper<>();
//        routeQueryWrapper.eq("is_delete", 0);
//        return routeMapper.selectList(routeQueryWrapper);
        return routeResult;
    }

    @Override
    public List<ResultRoute> calculateOne(String areaName, String apiKey, int assignNumber) throws Exception{
//        //获取全部聚集区
//        QueryWrapper<Accumulation> queryWrapper = new QueryWrapper<>();
//        queryWrapper.eq("is_delete", 0);
//        List<Accumulation> accumulations = accumulationMapper.selectList(queryWrapper);
//
//        //获取所有启用的中转场
//        QueryWrapper<TransitDepot> queryWrapper1 = new QueryWrapper<>();
//        queryWrapper1.eq("status", 1);
//        List<TransitDepot> transitDepots = transitDepotMapper.selectList(queryWrapper1);
//
//        // 将每个聚集区划分到最近的中转站
//        for (Accumulation accumulation : accumulations) {
//            double[] d1 = new double[]{accumulation.getLongitude(), accumulation.getLatitude()};
//            double distance = Double.MAX_VALUE;
//
//            int flag = 0;
//            for (int j = 0; j < transitDepots.size(); j++) {
//                TransitDepot transitDepot = transitDepots.get(j);
//                double[] d2 = new double[]{Double.parseDouble(transitDepot.getLongitude()), Double.parseDouble(transitDepot.getLatitude())};
//                double v = calculateEuclideanDistance(d1, d2);
//                if (v < distance) {
//                    distance = v;
//                    flag = j;
//                }
//            }
//
//            TransitDepot transitDepot = transitDepots.get(flag);
//
//            UpdateWrapper<Accumulation> updateWrapper = new UpdateWrapper<>();
//            updateWrapper.eq("accumulation_id", accumulation.getAccumulationId()).eq("is_delete", 0).set("transit_depot_id", transitDepot.getTransitDepotId());
//            accumulationMapper.update(null, updateWrapper);
//        }

        //得到当前要计算的区域的中转站
        accumulationUtils.updateAccumulationToDepot();
        TransitDepot transitDepot = transitDepotMapper.selectByName(areaName);

        Long transitDepotId = transitDepot.getTransitDepotId();
        Long areaId = transitDepot.getAreaId();
        String transitDepotName = transitDepot.getTransitDepotName();

        //获取当前中转站所有的车
        QueryWrapper<Car> carQueryWrapper = new QueryWrapper<>();
        carQueryWrapper.eq("transit_depot_id", transitDepotId).eq("status", "1");
        List<Car> cars = carMapper.selectList(carQueryWrapper);

        QueryWrapper<Accumulation> queryWrapper2 = new QueryWrapper<>();
        queryWrapper2.eq("transit_depot_id", transitDepotId).eq("is_delete", 0);
        List<Accumulation> accumulations1 = accumulationMapper.selectList(queryWrapper2);

        List<LngAndLat> lngAndLats = new ArrayList<>();
        for (Accumulation a : accumulations1) {
            lngAndLats.add(new LngAndLat(a.getLongitude(), a.getLatitude()));
        }

        //进行计算并处理返回的结果
        List<ResultRoute> routeResult = new ArrayList<>();
        Map<List<String>, Double> result = calculate(assignNumber, lngAndLats, transitDepotId, new double[]{Double.parseDouble(transitDepot.getLongitude()), Double.parseDouble(transitDepot.getLatitude())}, apiKey);
        Set<Map.Entry<List<String>, Double>> entries = result.entrySet();
        List<String> paths = new ArrayList<>();

        double distance = 0;
        //count和k用于对路线进行命名
        int count = 1;
        int k = 0;

        for (Map.Entry<List<String>, Double> m : entries) {
            double cargoWeight = 0;
            paths = m.getKey();
            distance = m.getValue();

            //将每一条路线做一下格式转换，然后存到数据库
            StringBuilder stringBuilder = new StringBuilder();
            for (int j = 0; j < paths.size(); j++) {
                String path = paths.get(j);

                if (j == paths.size() - 1) {
                    stringBuilder.append(path);
                } else {
                    stringBuilder.append(path);
                    stringBuilder.append(";");
                }
            }

            //遍历这条路径，计算出载货量（从中转站出发，再回到中转站）
            List<LngAndLat> polyLine = new ArrayList<>();
            String[] split = stringBuilder.toString().split(";");
            String[] origin = split[0].split(",");
            polyLine.add(new LngAndLat(Double.parseDouble(origin[0]), Double.parseDouble(origin[1])));
            for (int i1 = 1; i1 < split.length - 1; i1++) {
                String[] split1 = split[i1].split(",");

                QueryWrapper<Store> storeQueryWrapper = new QueryWrapper<>();
                try {
                    storeQueryWrapper.eq("longitude", split1[0]).eq("latitude", split1[1]);
                } catch (ArrayIndexOutOfBoundsException a) {
                    continue;
                }
                Store store = new Store();
                try {
                    store = storeMapper.selectList(storeQueryWrapper).get(0);
                } catch (IndexOutOfBoundsException a) {
                    throw new IllegalArgumentException(String.format(split1[0], split1[1]));
                }
                if (store == null) {
                    continue;
                }

                if (store.getGear() == null) {
                    continue;
                }
                QueryWrapper<Gear> gearQueryWrapper = new QueryWrapper<>();
                gearQueryWrapper.eq("gear_name", store.getGear());
                Gear gear = gearMapper.selectOne(gearQueryWrapper);

                cargoWeight += Double.parseDouble(gear.getCargoWeight());

                polyLine.add(new LngAndLat(Double.parseDouble(split1[0]), Double.parseDouble(split1[1])));
            }
            polyLine.add(new LngAndLat(Double.parseDouble(origin[0]), Double.parseDouble(origin[1])));
            //并计算除去中转站的凸包
            LngAndLat[] clist = new LngAndLat[polyLine.size() - 2];
            for (int i = 1; i < polyLine.size() - 1; i++) {
                int j = i - 1;
                clist[j] = polyLine.get(i);
            }
            List<LngAndLat> convex = null;
            if (polyLine.size() <= 5) {
                convex = polyLine;
                convex.remove(convex.size() - 1);
                convex.remove(0);
            } else {
                convex = ConvexHull.convexHull(clist);
            }
            convex.add(convex.get(0));

            //遍历这条路径，计算出载货量（起点和终点不再是中转站）
//            List<LngAndLat> polyLine = new ArrayList<>();
//            String[] split = stringBuilder.toString().split(";");
//            for (int i1 = 1; i1 < split.length - 1; i1++) {
//                String[] split1 = split[i1].split(",");
//
//                QueryWrapper<Store> storeQueryWrapper = new QueryWrapper<>();
//                try {
//                    storeQueryWrapper.eq("longitude", split1[0]).eq("latitude", split1[1]);
//                } catch (ArrayIndexOutOfBoundsException a) {
//                    continue;
//                }
//                Store store = new Store();
//                try {
//                    store = storeMapper.selectList(storeQueryWrapper).get(0);
//                } catch (IndexOutOfBoundsException a) {
//                    throw new IllegalArgumentException(String.format(split1[0], split1[1]));
//                }
//                if (store == null) {
//                    continue;
//                }
//
//                if (store.getGear() == null) {
//                    continue;
//                }
//                QueryWrapper<Gear> gearQueryWrapper = new QueryWrapper<>();
//                gearQueryWrapper.eq("gear_name", store.getGear());
//                Gear gear = gearMapper.selectOne(gearQueryWrapper);
//
//                cargoWeight += Double.parseDouble(gear.getCargoWeight());
//
//                polyLine.add(new LngAndLat(Double.parseDouble(split1[0]), Double.parseDouble(split1[1])));
//            }
//            LngAndLat[] list = new LngAndLat[polyLine.size()];
//            for(int i = 0; i < polyLine.size(); i++){
//                list[i] = polyLine.get(i);
//            }
//            polyLine = ConvexHull.convexHull(list);
//            polyLine.add(polyLine.get(0));

//            Route route = new Route();
//            route.setPolyline(stringBuilder.toString());
//            route.setTransitDepotId(transitDepotId);
//            route.setRouteName(transitDepot.getTransitDepotName() + i);
//            route.setDistance(String.valueOf(distance));
//            route.setCargoWeight(String.valueOf(cargoWeight));
//                routeMapper.insert(route);
//            routeResult.add(route);

            String licensePlateNumber = null;
            try {
                licensePlateNumber = cars.get(k).getLicensePlateNumber();
            } catch (IndexOutOfBoundsException e) {
                throw new CarNumberException("车辆数不足，无法继续计算");
            }
            String day = null;
            switch (count) {
                case 1:
                    day = "星期一";
                    break;
                case 2:
                    day = "星期二";
                    break;
                case 3:
                    day = "星期三";
                    break;
                case 4:
                    day = "星期四";
                    break;
                case 5:
                    day = "星期五";
                    break;
            }
            // 获取当前时间
            LocalDateTime currentTime = LocalDateTime.now();
            // 定义日期时间格式
            DateTimeFormatter formatter = DateTimeFormatter.ofPattern("yyyy.MM.dd");
            // 格式化当前时间
            String formattedTime = currentTime.format(formatter);

            ResultRoute resultRoute = new ResultRoute();
            resultRoute.setPolyline(polyLine);
            resultRoute.setTransitDepotId(transitDepotId);
            resultRoute.setRouteName(transitDepotName + "-" + licensePlateNumber + "-" + day + "-" + formattedTime);
            resultRoute.setDistance(String.format("%.2f", distance));
            resultRoute.setCargoWeight(String.format("%.2f", cargoWeight));
            resultRoute.setAreaId(areaId);
//            resultRoute.setWorkTime(BigDecimal.valueOf(Double.parseDouble(String.format("%.2f", distance / 36))));
            resultRoute.setConvex(convex);
            routeResult.add(resultRoute);

            //对命名的星期几进行操作
            if (++count == 6) {
                count = 1;
                k++;
            }
        }

        return routeResult;
    }

    @Override
    public List<ResultRoute> calculateSingleRoute(String routeName, String apiKey) {
        QueryWrapper<Route> routeQueryWrapper = new QueryWrapper<>();
        routeQueryWrapper.eq("is_delete", 0).eq("route_name", routeName);
        Route route = routeMapper.selectOne(routeQueryWrapper);

        QueryWrapper<Accumulation> accumulationQueryWrapper = new QueryWrapper<>();
        accumulationQueryWrapper.eq("is_delete", 0).eq("route_id", route.getRouteId());
        List<Accumulation> accumulations = accumulationMapper.selectList(accumulationQueryWrapper);

        QueryWrapper<TransitDepot> transitDepotQueryWrapper = new QueryWrapper<>();
        transitDepotQueryWrapper.eq("transit_depot_id", route.getTransitDepotId()).eq("status", 1);
        TransitDepot transitDepot = transitDepotMapper.selectOne(transitDepotQueryWrapper);

        List<LngAndLat> lngAndLats = new ArrayList<>();
        for (Accumulation a : accumulations) {
            lngAndLats.add(new LngAndLat(a.getLongitude(), a.getLatitude()));
        }

        //进行计算并处理返回的结果
        List<ResultRoute> routeResult = new ArrayList<>();
        Map<List<String>, Double> result = calculate(1, lngAndLats, route.getTransitDepotId(), new double[]{Double.parseDouble(transitDepot.getLongitude()), Double.parseDouble(transitDepot.getLatitude())}, apiKey);
        Set<Map.Entry<List<String>, Double>> entries = result.entrySet();
        List<String> paths = new ArrayList<>();

        double distance = 0;

        for (Map.Entry<List<String>, Double> m : entries) {
            double cargoWeight = 0;
            paths = m.getKey();
            distance = m.getValue();

            //将每一条路线做一下格式转换，然后存到数据库
            StringBuilder stringBuilder = new StringBuilder();
            for (int j = 0; j < paths.size(); j++) {
                String path = paths.get(j);

                if (j == paths.size() - 1) {
                    stringBuilder.append(path);
                } else {
                    stringBuilder.append(path);
                    stringBuilder.append(";");
                }
            }

            //遍历这条路径，计算出载货量（从中转站出发，再回到中转站）
            List<LngAndLat> polyLine = new ArrayList<>();
            String[] split = stringBuilder.toString().split(";");
            String[] origin = split[0].split(",");
            polyLine.add(new LngAndLat(Double.parseDouble(origin[0]), Double.parseDouble(origin[1])));
            for (int i1 = 1; i1 < split.length - 1; i1++) {
                String[] split1 = split[i1].split(",");

                QueryWrapper<Store> storeQueryWrapper = new QueryWrapper<>();
                try {
                    storeQueryWrapper.eq("longitude", split1[0]).eq("latitude", split1[1]);
                } catch (ArrayIndexOutOfBoundsException a) {
                    continue;
                }
                Store store = new Store();
                try {
                    store = storeMapper.selectList(storeQueryWrapper).get(0);
                } catch (IndexOutOfBoundsException a) {
                    throw new IllegalArgumentException(String.format(split1[0], split1[1]));
                }
                if (store == null) {
                    continue;
                }

                if (store.getGear() == null) {
                    continue;
                }
                QueryWrapper<Gear> gearQueryWrapper = new QueryWrapper<>();
                gearQueryWrapper.eq("gear_name", store.getGear());
                Gear gear = gearMapper.selectOne(gearQueryWrapper);

                cargoWeight += Double.parseDouble(gear.getCargoWeight());

                polyLine.add(new LngAndLat(Double.parseDouble(split1[0]), Double.parseDouble(split1[1])));
            }
            polyLine.add(new LngAndLat(Double.parseDouble(origin[0]), Double.parseDouble(origin[1])));
            //并计算除去中转站的凸包
            LngAndLat[] clist = new LngAndLat[polyLine.size() - 2];
            for (int i = 1; i < polyLine.size() - 1; i++) {
                int j = i - 1;
                clist[j] = polyLine.get(i);
            }
            List<LngAndLat> convex = null;
            if (polyLine.size() <= 5) {
                convex = polyLine;
                convex.remove(convex.size() - 1);
                convex.remove(0);
            } else {
                convex = ConvexHull.convexHull(clist);
            }
            convex.add(convex.get(0));


            ResultRoute resultRoute = new ResultRoute();
            resultRoute.setPolyline(polyLine);
            resultRoute.setDistance(String.format("%.2f", distance));
            resultRoute.setCargoWeight(String.format("%.2f", cargoWeight));
            resultRoute.setWorkTime(BigDecimal.valueOf(Double.parseDouble(String.format("%.2f", distance / 36))));
            resultRoute.setConvex(convex);
            resultRoute.setTransitDepotId(route.getTransitDepotId());
            resultRoute.setRouteName(route.getRouteName());
            resultRoute.setAreaId(route.getAreaId());
            routeResult.add(resultRoute);
        }

        return routeResult;
    }

//    private void updateAccumulationToDepot() {
//        QueryWrapper<TransitDepot> q1 = new QueryWrapper<>();
//        q1.like("transit_depot_name", "坪石").eq("status", 1);
//        TransitDepot t1 = transitDepotMapper.selectOne(q1);
//        UpdateWrapper<Accumulation> u1 = new UpdateWrapper<>();
//        u1.like("area_name", "乐昌").eq("is_delete", 0).set("transit_depot_id", t1.getTransitDepotId());
//        accumulationMapper.update(null, u1);
//        UpdateWrapper<Accumulation> u2 = new UpdateWrapper<>();
//        u2.like("area_name", "大桥").eq("is_delete", 0).set("transit_depot_id", t1.getTransitDepotId());
//        accumulationMapper.update(null, u2);
//
//        QueryWrapper<TransitDepot> q2 = new QueryWrapper<>();
//        q2.like("transit_depot_name", "物流配送中心").eq("status", 1);
//        TransitDepot t2 = transitDepotMapper.selectOne(q2);
//        UpdateWrapper<Accumulation> u3 = new UpdateWrapper<>();
//        u3.like("area_name", "市辖区").eq("is_delete", 0).set("transit_depot_id", t2.getTransitDepotId());
//        accumulationMapper.update(null, u3);
//        UpdateWrapper<Accumulation> u4 = new UpdateWrapper<>();
//        u4.like("area_name", "曲江").eq("is_delete", 0).set("transit_depot_id", t2.getTransitDepotId());
//        accumulationMapper.update(null, u4);
//        UpdateWrapper<Accumulation> u5 = new UpdateWrapper<>();
//        u5.like("area_name", "铁龙").eq("is_delete", 0).set("transit_depot_id", t2.getTransitDepotId());
//        accumulationMapper.update(null, u5);
//        UpdateWrapper<Accumulation> u6 = new UpdateWrapper<>();
//        u6.like("area_name", "乳源").eq("is_delete", 0).set("transit_depot_id", t2.getTransitDepotId());
//        accumulationMapper.update(null, u6);
//        UpdateWrapper<Accumulation> u12 = new UpdateWrapper<>();
//        u12.like("area_name", "浈江").eq("is_delete", 0).set("transit_depot_id", t2.getTransitDepotId());
//        accumulationMapper.update(null, u12);
//        UpdateWrapper<Accumulation> u13 = new UpdateWrapper<>();
//        u13.like("area_name", "武江").eq("is_delete", 0).set("transit_depot_id", t2.getTransitDepotId());
//        accumulationMapper.update(null, u13);
//
//        QueryWrapper<TransitDepot> q3 = new QueryWrapper<>();
//        q3.like("transit_depot_name", "马市").eq("status", 1);
//        TransitDepot t3 = transitDepotMapper.selectOne(q3);
//        UpdateWrapper<Accumulation> u7 = new UpdateWrapper<>();
//        u7.like("area_name", "始兴").eq("is_delete", 0).set("transit_depot_id", t3.getTransitDepotId());
//        accumulationMapper.update(null, u7);
//        UpdateWrapper<Accumulation> u8 = new UpdateWrapper<>();
//        u8.like("area_name", "南雄").eq("is_delete", 0).set("transit_depot_id", t3.getTransitDepotId());
//        accumulationMapper.update(null, u8);
//
//        QueryWrapper<TransitDepot> q4 = new QueryWrapper<>();
//        q4.like("transit_depot_name", "翁源").eq("status", 1);
//        TransitDepot t4 = transitDepotMapper.selectOne(q4);
//        UpdateWrapper<Accumulation> u9 = new UpdateWrapper<>();
//        u9.like("area_name", "翁源").eq("is_delete", 0).set("transit_depot_id", t4.getTransitDepotId());
//        accumulationMapper.update(null, u9);
//
//        QueryWrapper<TransitDepot> q5 = new QueryWrapper<>();
//        q5.like("transit_depot_name", "新丰").eq("status", 1);
//        TransitDepot t5 = transitDepotMapper.selectOne(q5);
//        UpdateWrapper<Accumulation> u10 = new UpdateWrapper<>();
//        u10.like("area_name", "新丰").eq("is_delete", 0).set("transit_depot_id", t5.getTransitDepotId());
//        accumulationMapper.update(null, u10);
//
//        QueryWrapper<TransitDepot> q6 = new QueryWrapper<>();
//        q6.like("transit_depot_name", "仁化").eq("status", 1);
//        TransitDepot t6 = transitDepotMapper.selectOne(q6);
//        UpdateWrapper<Accumulation> u11 = new UpdateWrapper<>();
//        u11.like("area_name", "仁化").eq("is_delete", 0).set("transit_depot_id", t6.getTransitDepotId());
//        accumulationMapper.update(null, u11);
//    }

    public Map<List<String>, Double> calculate(int assignNumber, List<LngAndLat> lngAndLats, Long transitDepotId, double[] transitDepot, String apiKey) {
        // 对这个打破行政区的全部聚集区进行分簇，也就是划分路线
        List<CentroidCluster<DoublePoint>> centroidClusters = new ArrayList<>();

        if (assignNumber == 1) {
            CentroidCluster<DoublePoint> centroidCluster = new CentroidCluster<>(null);
            for (LngAndLat lngAndLat : lngAndLats) {
                centroidCluster.addPoint(new DoublePoint(new double[]{lngAndLat.getLongitude(), lngAndLat.getLatitude()}));
            }
            centroidClusters.add(centroidCluster);
        } else {
            while (true) {
                if (centroidClusters.size() == 0) {
                    List<CentroidCluster<DoublePoint>> centroidClusters1 = assignNumberOfCluster(2, lngAndLats);
                    centroidClusters.addAll(centroidClusters1);
                } else {
                    //找出当前centroidClusters里元素最多的簇
                    CentroidCluster<DoublePoint> temp = null;
                    int size = 0;
                    for (CentroidCluster<DoublePoint> c : centroidClusters) {
                        if (c.getPoints().size() > size) {
                            size = c.getPoints().size();
                            temp = c;
                        }
                    }
                    //再将这个元素最多的簇进行划分
                    List<LngAndLat> l1 = new ArrayList<>();
                    for (DoublePoint d : temp.getPoints()) {
                        l1.add(new LngAndLat(d.getPoint()[0], d.getPoint()[1]));
                    }
                    List<CentroidCluster<DoublePoint>> centroidClusters1 = assignNumberOfCluster(2, l1);
                    centroidClusters.remove(temp);
                    centroidClusters.addAll(centroidClusters1);
                }

                if (centroidClusters.size() == assignNumber) {
                    break;
                }
            }
        }

        Map<List<String>, Double> result = new LinkedHashMap<>();

        for (CentroidCluster<DoublePoint> doublePointCentroidCluster : centroidClusters) {
            //获取当前路线所包含的所有聚集区
            List<DoublePoint> points = doublePointCentroidCluster.getPoints();

            //对这条路线的聚集区再分簇，得到每条小路线，目的是为了减少api的调用次数
//            int ceilK = (int) (Math.floor(points.size() / 5) + 1);

            List<LngAndLat> lngAndLats1 = new ArrayList<>();
            for (DoublePoint d : points) {
                lngAndLats1.add(new LngAndLat(d.getPoint()[0], d.getPoint()[1]));
            }
//
//            List<CentroidCluster<DoublePoint>> centroidClusters1 = assignNumberOfCluster(ceilK, lngAndLats1);

            if (points.size() < 10) {
                points.add(new DoublePoint(new double[]{transitDepot[0], transitDepot[1]}));

                double[][] distanceMatrix = new double[points.size()][points.size()];
                for (int i = 0; i < points.size(); i++) {
                    for (int j = 0; j < points.size(); j++) {
                        distanceMatrix[i][j] = Double.MAX_VALUE;
                    }
                }
                String[][] pointsMatrix = new String[points.size()][points.size()];
                for (int k = 0; k < points.size(); k++) {
                    for (int m = 0; m < points.size(); m++) {
                        //如果k和m相同就不用获取距离了，因为都是同一个点
                        if (k == m) {
                            continue;
                        }

                        //获取当前循环里某两个点的距离，并存储到ordinaryDistanceMatrix和ordinaryPointMatrix
                        String origin = points.get(k).getPoint()[0] + "," + points.get(k).getPoint()[1];
                        String destination = points.get(m).getPoint()[0] + "," + points.get(m).getPoint()[1];
                        QueryWrapper<PointDistance> queryWrapper = new QueryWrapper<>();
                        queryWrapper.eq("origin", origin).eq("destination", destination).eq("is_delete", 0);
                        List<PointDistance> list = pointDistanceMapper.selectList(queryWrapper);
                        if (list.size() == 0) {
                            double dis = saveDistanceInformation(points.get(k), points.get(m), transitDepotId, "ordinary", apiKey);
                            distanceMatrix[k][m] = dis;
                            pointsMatrix[k][m] = origin + ";" + destination;
                        } else {
                            distanceMatrix[k][m] = Double.parseDouble(list.get(0).getDistance());
                            pointsMatrix[k][m] = list.get(0).getOrigin() + ";" + list.get(0).getDestination();
                        }
                    }
                }

                //计算小路线和中转站的最短路径
                List<Integer> path = null;
                double v = Double.MAX_VALUE;
                for (int iii = 0; iii < points.size() - 1; iii++) {
                    List<Integer> temp = calculatePartialPath(distanceMatrix, points.size() - 1, iii);
                    double dis = totalDistance(temp, distanceMatrix);
                    //再加上最后一个点到中转站的距离,points.size() - 1表示中转站的索引
                    dis += distanceMatrix[temp.get(temp.size() - 1)][points.size() - 1];

                    if (dis < v) {
                        v = dis;
                        temp.add(points.size() - 1);
                        path = temp;
                    }
                }

                //将得到的path做转换为坐标串，作为当前路线的骨架
                List<String> basePath = new ArrayList<>();
                for (int j = 0; j < path.size() - 1; j++) {
                    String twoPointBridge = pointsMatrix[path.get(j)][path.get(j + 1)];
                    String[] splits = twoPointBridge.split(";");
                    if (j == path.size() - 1 - 1) {
                        basePath.add(splits[0]);
                        basePath.add(splits[1]);
                    } else {
                        basePath.add(splits[0]);
                    }
                }
//                List<String> finalPath = new ArrayList<>(basePath);
//                for (int i = 0; i < basePath.size(); i++) {
//                    if (i == basePath.size() - 1) {
//                        finalPath.add(basePath.get(i));
//                    } else {
//                        finalPath.add(basePath.get(i));
//                        finalPath.add(";");
//                    }
//                }

                //存最终路线和对应的距离
                result.put(basePath, v);
            } else {
                List<CentroidCluster<DoublePoint>> centroidClusters1 = new ArrayList<>();
                while (true) {
                    int flag = 0;

                    if (centroidClusters1.size() == 0) {
                        List<CentroidCluster<DoublePoint>> centroidClusters3 = assignNumberOfCluster(2, lngAndLats1);
                        centroidClusters1.addAll(centroidClusters3);
                    } else {
                        //找出当前centroidClusters里元素最多的簇
                        CentroidCluster<DoublePoint> temp = null;
                        int size = 0;
                        for (CentroidCluster<DoublePoint> c : centroidClusters1) {
                            if (c.getPoints().size() > size) {
                                size = c.getPoints().size();
                                temp = c;
                            }
                        }
                        //再将这个元素最多的簇进行划分
                        List<LngAndLat> l1 = new ArrayList<>();
                        for (DoublePoint d : temp.getPoints()) {
                            l1.add(new LngAndLat(d.getPoint()[0], d.getPoint()[1]));
                        }
                        List<CentroidCluster<DoublePoint>> centroidClusters3 = assignNumberOfCluster(2, l1);
                        centroidClusters1.remove(temp);
                        centroidClusters1.addAll(centroidClusters3);
                    }

                    //如果每个小路线里的元素小于10了，即使centroidClusters.size()不等于10，也可以退出while循环
                    for (CentroidCluster<DoublePoint> c : centroidClusters1) {
                        if (c.getPoints().size() <= 9) {
                            flag++;
                        }
                    }

                    if (centroidClusters1.size() == 8 || flag == centroidClusters1.size()) {
                        break;
                    }
                }

                double[][] bridgeDistanceMatrix = new double[centroidClusters1.size() + 1][centroidClusters1.size() + 1];
                for (int i = 0; i < centroidClusters1.size() + 1; i++) {
                    for (int j = 0; j < centroidClusters1.size() + 1; j++) {
                        bridgeDistanceMatrix[i][j] = Double.MAX_VALUE;
                    }
                }
                String[][] bridgePointsMatrix = new String[centroidClusters1.size() + 1][centroidClusters1.size() + 1];
                for (int ii = 0; ii < centroidClusters1.size() - 1; ii++) {
                    //两两小路线的距离
                    for (int jj = ii + 1; jj < centroidClusters1.size(); jj++) {
                        List<DoublePoint> points1 = centroidClusters1.get(ii).getPoints();
                        List<DoublePoint> points2 = centroidClusters1.get(jj).getPoints();

                        double dist1 = Double.MAX_VALUE;
                        DoublePoint origin1 = null;
                        DoublePoint destination1 = null;
                        for (DoublePoint d1 : points1) {
                            for (DoublePoint d2 : points2) {
                                double v = calculateEuclideanDistance(d1.getPoint(), d2.getPoint());
                                if (v < dist1) {
                                    dist1 = v;
                                    origin1 = d1;
                                    destination1 = d2;
                                }
                            }
                        }
                        //存储这两个小路线之间的双向距离到数据库和距离矩阵
                        QueryWrapper<PointDistance> q1 = new QueryWrapper<>();
                        q1.eq("origin", origin1.getPoint()[0] + "," + origin1.getPoint()[1]).eq("destination", destination1.getPoint()[0] + "," + destination1.getPoint()[1]).eq("is_delete", 0);
                        List<PointDistance> l1 = pointDistanceMapper.selectList(q1);
                        double distance1 = 0;
                        if (l1.size() == 0) {
                            double d1 = saveDistanceInformation(origin1, destination1, transitDepotId, "bridge", apiKey);
                            distance1 = d1;
                        } else {
                            PointDistance pointDistance = l1.get(0);
                            distance1 = Double.parseDouble(pointDistance.getDistance());
                        }

                        QueryWrapper<PointDistance> q2 = new QueryWrapper<>();
                        q2.eq("origin", destination1.getPoint()[0] + "," + destination1.getPoint()[1]).eq("destination", origin1.getPoint()[0] + "," + origin1.getPoint()[1]).eq("is_delete", 0);
                        List<PointDistance> l2 = pointDistanceMapper.selectList(q2);
                        double distance2 = 0;
                        if (l2.size() == 0) {
                            double d2 = saveDistanceInformation(destination1, origin1, transitDepotId, "bridge", apiKey);
                            distance2 = d2;
                        } else {
                            PointDistance pointDistance = l2.get(0);
                            distance2 = Double.parseDouble(pointDistance.getDistance());
                        }

                        bridgeDistanceMatrix[ii][jj] = distance1;
                        bridgeDistanceMatrix[jj][ii] = distance2;
                        bridgePointsMatrix[ii][jj] = (origin1.getPoint()[0] + "," + origin1.getPoint()[1]) + ";" + (destination1.getPoint()[0] + "," + destination1.getPoint()[1]);
                        bridgePointsMatrix[jj][ii] = (destination1.getPoint()[0] + "," + destination1.getPoint()[1]) + ";" + (origin1.getPoint()[0] + "," + origin1.getPoint()[1]);
                    }

                    //当前小路线和中转站的距离
                    if (ii == centroidClusters1.size() - 1 - 1) {
                        List<DoublePoint> points1 = centroidClusters1.get(ii).getPoints();
                        calculateBridgeWithTransitDepot(transitDepotId, transitDepot, centroidClusters1.size(), bridgeDistanceMatrix, ii, points1, bridgePointsMatrix, apiKey);
                        points1 = centroidClusters1.get(ii + 1).getPoints();
                        calculateBridgeWithTransitDepot(transitDepotId, transitDepot, centroidClusters1.size(), bridgeDistanceMatrix, ii + 1, points1, bridgePointsMatrix, apiKey);
                    } else {
                        List<DoublePoint> points1 = centroidClusters1.get(ii).getPoints();
                        calculateBridgeWithTransitDepot(transitDepotId, transitDepot, centroidClusters1.size(), bridgeDistanceMatrix, ii, points1, bridgePointsMatrix, apiKey);
                    }
                }

                //计算小路线和中转站的最短路径
                List<Integer> path = null;
                double v = Double.MAX_VALUE;
                for (int iii = 0; iii < centroidClusters1.size(); iii++) {
                    List<Integer> temp = calculatePartialPath(bridgeDistanceMatrix, centroidClusters1.size(), iii);
                    double dis = totalDistance(temp, bridgeDistanceMatrix);
                    //再加上最后一个点到中转站的距离,centroidClusters1.size()表示中转站的索引
                    dis += bridgeDistanceMatrix[temp.get(temp.size() - 1)][centroidClusters1.size()];

                    if (dis < v) {
                        v = dis;
                        temp.add(centroidClusters1.size());
                        path = temp;
                    }
                }

                //将得到的path做转换为坐标串，作为当前路线的骨架
                List<String> basePath = new ArrayList<>();
                for (int j = 0; j < path.size() - 1; j++) {
                    String twoPointBridge = bridgePointsMatrix[path.get(j)][path.get(j + 1)];
                    String[] splits = twoPointBridge.split(";");
                    basePath.addAll(Arrays.asList(splits));
                }
                List<String> finalPath = new ArrayList<>(basePath);

                //获取每条小路线里的聚集区的两两距离，并通过basePath来串联每个小路线，得到计算完的当前这一整条路线
                double v1 = 0;
                for (int j = 0; j < centroidClusters1.size(); j++) {
                    List<DoublePoint> points1 = centroidClusters1.get(j).getPoints();

                    if (points1.size() == 1) {
                        continue;
                    }

                    if (points1.size() > 9) {
                        //找当前小路线的起点的坐标和终点的坐标
                        int flag = 0;
                        for (int l1 = 1; l1 < basePath.size() - 1; l1++) {
                            String[] split = basePath.get(l1).split(",");
                            DoublePoint doublePoint = new DoublePoint(new double[]{Double.parseDouble(split[0]), Double.parseDouble(split[1])});
                            if (points1.contains(doublePoint)) {
                                flag = l1;
                                break;
                            }
                        }
                        String startPoint = basePath.get(flag);
                        String endPoint = basePath.get(flag + 1);

                        List<CentroidCluster<DoublePoint>> p = new ArrayList<>();
                        List<LngAndLat> l = new ArrayList<>();
                        for (DoublePoint d : points1) {
                            l.add(new LngAndLat(d.getPoint()[0], d.getPoint()[1]));
                        }
                        while (true) {
                            int f = 0;

                            if (p.size() == 0) {
                                List<CentroidCluster<DoublePoint>> c = assignNumberOfCluster(2, l);
                                p.addAll(c);
                            } else {
                                //找出当前centroidClusters里元素最多的簇
                                CentroidCluster<DoublePoint> temp = null;
                                int size = 0;
                                for (CentroidCluster<DoublePoint> c : p) {
                                    if (c.getPoints().size() > size) {
                                        size = c.getPoints().size();
                                        temp = c;
                                    }
                                }
                                //再将这个元素最多的簇进行划分
                                List<LngAndLat> l1 = new ArrayList<>();
                                for (DoublePoint d : temp.getPoints()) {
                                    l1.add(new LngAndLat(d.getPoint()[0], d.getPoint()[1]));
                                }
                                List<CentroidCluster<DoublePoint>> c1 = assignNumberOfCluster(2, l1);
                                p.remove(temp);
                                p.addAll(c1);
                            }

                            //如果每个小路线里的元素小于10了，即使centroidClusters.size()不等于10，也可以退出while循环
                            for (CentroidCluster<DoublePoint> c : p) {
                                if (c.getPoints().size() <= 9) {
                                    f++;
                                }
                            }

                            if (p.size() == 8 || f == p.size()) {
                                break;
                            }
                        }

                        //分完簇后，找到startPoint和endPoint所在的簇
                        int startCluster = 0;
                        int endCluster = 0;
                        String[] split = startPoint.split(",");
                        String[] split1 = endPoint.split(",");
                        for (int e = 0; e < p.size(); e++) {
                            if (p.get(e).getPoints().contains(new DoublePoint(new double[]{Double.parseDouble(split[0]), Double.parseDouble(split[1])}))) {
                                startCluster = e;
                            }

                            if (p.get(e).getPoints().contains(new DoublePoint(new double[]{Double.parseDouble(split1[0]), Double.parseDouble(split1[1])}))) {
                                endCluster = e;
                            }
                        }

                        //先计算这种特殊情况的小路线的分簇路线
                        double[][] smallDistanceMatrix = new double[p.size()][p.size()];
                        for (int i = 0; i < p.size(); i++) {
                            for (int k = 0; k < p.size(); k++) {
                                smallDistanceMatrix[i][k] = Double.MAX_VALUE;
                            }
                        }
                        String[][] smallPointMatrix = new String[p.size()][p.size()];
                        for (int ii = 0; ii < p.size() - 1; ii++) {
                            //两两小路线的距离
                            for (int jj = ii + 1; jj < p.size(); jj++) {
                                List<DoublePoint> p1 = p.get(ii).getPoints();
                                List<DoublePoint> p2 = p.get(jj).getPoints();

                                double dist1 = Double.MAX_VALUE;
                                DoublePoint origin1 = null;
                                DoublePoint destination1 = null;
                                for (DoublePoint d1 : p1) {
                                    for (DoublePoint d2 : p2) {
                                        double smallV = calculateEuclideanDistance(d1.getPoint(), d2.getPoint());
                                        if (smallV < dist1) {
                                            dist1 = smallV;
                                            origin1 = d1;
                                            destination1 = d2;
                                        }
                                    }
                                }
                                //存储这两个小路线之间的双向距离到数据库和距离矩阵
                                QueryWrapper<PointDistance> q1 = new QueryWrapper<>();
                                q1.eq("origin", origin1.getPoint()[0] + "," + origin1.getPoint()[1]).eq("destination", destination1.getPoint()[0] + "," + destination1.getPoint()[1]).eq("is_delete", 0);
                                List<PointDistance> l1 = pointDistanceMapper.selectList(q1);
                                double distance1 = 0;
                                if (l1.size() == 0) {
                                    distance1 = saveDistanceInformation(origin1, destination1, transitDepotId, "bridge", apiKey);
                                } else {
                                    PointDistance pointDistance = l1.get(0);
                                    distance1 = Double.parseDouble(pointDistance.getDistance());
                                }

                                QueryWrapper<PointDistance> q2 = new QueryWrapper<>();
                                q2.eq("origin", destination1.getPoint()[0] + "," + destination1.getPoint()[1]).eq("destination", origin1.getPoint()[0] + "," + origin1.getPoint()[1]).eq("is_delete", 0);
                                List<PointDistance> l2 = pointDistanceMapper.selectList(q2);
                                double distance2 = 0;
                                if (l2.size() == 0) {
                                    distance2 = saveDistanceInformation(destination1, origin1, transitDepotId, "bridge", apiKey);
                                } else {
                                    PointDistance pointDistance = l2.get(0);
                                    distance2 = Double.parseDouble(pointDistance.getDistance());
                                }

                                smallDistanceMatrix[ii][jj] = distance1;
                                smallDistanceMatrix[jj][ii] = distance2;
                                smallPointMatrix[ii][jj] = (origin1.getPoint()[0] + "," + origin1.getPoint()[1]) + ";" + (destination1.getPoint()[0] + "," + destination1.getPoint()[1]);
                                smallPointMatrix[jj][ii] = (destination1.getPoint()[0] + "," + destination1.getPoint()[1]) + ";" + (origin1.getPoint()[0] + "," + origin1.getPoint()[1]);
                            }
                        }

                        //如果存在startCluster == endCluster，即入口和出口都在同一个簇的情况
                        List<Integer> pCluster = new ArrayList<>();
                        if (startCluster == endCluster) {
                            double mostV = Double.MAX_VALUE;
                            for (int iii = 0; iii < p.size(); iii++) {
                                if (iii == startCluster) {
                                    continue;
                                }
                                List<Integer> temp = calculatePartialPath(smallDistanceMatrix, startCluster, iii);
                                double dis = totalDistance(temp, smallDistanceMatrix);
                                //再加上最后一个点到中转站的距离,centroidClusters1.size()表示中转站的索引
                                dis += smallDistanceMatrix[temp.get(temp.size() - 1)][startCluster];

                                if (dis < mostV) {
                                    mostV = dis;
                                    temp.add(startCluster);
                                    pCluster = temp;
                                }
                            }
                            v1 += mostV;
                        } else {
                            pCluster = calculatePartialPath(smallDistanceMatrix, startCluster, endCluster);
                            v1 += totalDistance(pCluster, smallDistanceMatrix);
                        }

                        //根据pCluster来串起这种情况的路径
                        StringBuilder stringBuilder = new StringBuilder();
                        String lastStartP = "";
                        for (int i = 0; i < pCluster.size(); i++) {
                            //当前簇的起点
                            String startP = "";
                            //当前簇的终点
                            String endP = "";
                            if (i == pCluster.size() - 1) {
                                endP = endPoint;
                                startP = lastStartP;
                            } else {
                                //获取当前簇和下一个簇的连接点对
                                String pointss = smallPointMatrix[pCluster.get(i)][pCluster.get(i + 1)];
                                String[] split2 = pointss.split(";");

                                endP = split2[0];
                                if (i == 0) {
                                    startP = startPoint;
                                } else {
                                    startP = lastStartP;
                                }
                                //作为下一个簇的起点
                                lastStartP = split2[1];
                            }


                            //获取当前簇
                            CentroidCluster<DoublePoint> currCluster = p.get(pCluster.get(i));

                            double[][] ssDistanceMatrix = new double[currCluster.getPoints().size()][currCluster.getPoints().size()];
                            for (int i1 = 0; i1 < currCluster.getPoints().size(); i1++) {
                                for (int k = 0; k < currCluster.getPoints().size(); k++) {
                                    ssDistanceMatrix[i1][k] = Double.MAX_VALUE;
                                }
                            }
                            String[][] ssPointMatrix = new String[currCluster.getPoints().size()][currCluster.getPoints().size()];

                            int startIndex = 0;
                            int endIndex = 0;
                            for (int k = 0; k < currCluster.getPoints().size(); k++) {
                                if ((currCluster.getPoints().get(k).getPoint()[0] + "," + currCluster.getPoints().get(k).getPoint()[1]).equals(startP)) {
                                    startIndex = k;
                                }
                                if ((currCluster.getPoints().get(k).getPoint()[0] + "," + currCluster.getPoints().get(k).getPoint()[1]).equals(endP)) {
                                    endIndex = k;
                                }
                                for (int m = 0; m < currCluster.getPoints().size(); m++) {
                                    //如果k和m相同就不用获取距离了，因为都是同一个点
                                    if (k == m) {
                                        continue;
                                    }

                                    //获取当前循环里某两个点的距离，并存储到ordinaryDistanceMatrix和ordinaryPointMatrix
                                    String origin = currCluster.getPoints().get(k).getPoint()[0] + "," + currCluster.getPoints().get(k).getPoint()[1];
                                    String destination = currCluster.getPoints().get(m).getPoint()[0] + "," + currCluster.getPoints().get(m).getPoint()[1];
                                    QueryWrapper<PointDistance> queryWrapper = new QueryWrapper<>();
                                    queryWrapper.eq("origin", origin).eq("destination", destination).eq("is_delete", 0);
                                    List<PointDistance> list = pointDistanceMapper.selectList(queryWrapper);
                                    if (list.size() == 0) {
                                        double dis = saveDistanceInformation(currCluster.getPoints().get(k), currCluster.getPoints().get(m), transitDepotId, "ordinary", apiKey);
                                        ssDistanceMatrix[k][m] = dis;
                                        ssPointMatrix[k][m] = origin + ";" + destination;
                                    } else {
                                        ssDistanceMatrix[k][m] = Double.parseDouble(list.get(0).getDistance());
                                        ssPointMatrix[k][m] = list.get(0).getOrigin() + ";" + list.get(0).getDestination();
                                    }
                                }
                            }

                            List<Integer> paths = new ArrayList<>();
                            if (startIndex == endIndex) {
                                double mostV = Double.MAX_VALUE;
                                for (int iii = 0; iii < currCluster.getPoints().size(); iii++) {
                                    if (iii == startIndex) {
                                        continue;
                                    }
                                    List<Integer> temp = calculatePartialPath(ssDistanceMatrix, startIndex, iii);
                                    double dis = totalDistance(temp, ssDistanceMatrix);
                                    //再加上最后一个点到中转站的距离,centroidClusters1.size()表示中转站的索引
                                    dis += ssDistanceMatrix[temp.get(temp.size() - 1)][startIndex];

                                    if (dis < mostV) {
                                        mostV = dis;
                                        temp.add(startIndex);
                                        paths = temp;
                                    }
                                }
                                v1 += mostV;
                            } else {
                                paths = calculatePartialPath(ssDistanceMatrix, startIndex, endIndex);
                                v1 += totalDistance(paths, ssDistanceMatrix);
                            }


                            for (int k = 0; k < paths.size() - 1; k++) {
                                if (k == paths.size() - 1 - 1) {
//                        String twoPoint = ordinaryPointMatrix[tPath.get(k - 1)][tPath.get(k)];
                                    String twoPoint = ssPointMatrix[paths.get(k)][paths.get(k + 1)];
                                    String[] sp = twoPoint.split(";");
                                    stringBuilder.append(sp[0]);
                                    stringBuilder.append(";");
                                    stringBuilder.append(sp[1]);
                                } else {
                                    String twoPoint = ssPointMatrix[paths.get(k)][paths.get(k + 1)];
                                    String[] sp = twoPoint.split(";");
                                    stringBuilder.append(sp[0]);
                                    stringBuilder.append(";");
                                }
                            }

                            if (i != pCluster.size() - 1) {
                                stringBuilder.append(";");
                            }
                        }
                        //加入到最终路径里
                        for (int l1 = 1; l1 < finalPath.size() - 1; l1++) {
                            String[] split2 = finalPath.get(l1).split(";");
                            if (split2.length > 1) {
                                continue;
                            }
                            String[] s = finalPath.get(l1).split(",");
                            DoublePoint doublePoint = new DoublePoint(new double[]{Double.parseDouble(s[0]), Double.parseDouble(s[1])});
                            if (points1.contains(doublePoint)) {
                                flag = l1;
                                break;
                            }
                        }
                        int removedFirst = stringBuilder.indexOf(";");
                        int removedLast = stringBuilder.lastIndexOf(";");
                        stringBuilder.delete(removedLast, stringBuilder.length());
                        stringBuilder.delete(0, removedFirst + 1);

                        finalPath.add(flag + 1, stringBuilder.toString());

                    } else {
                        double[][] ordinaryDistanceMatrix = new double[points1.size()][points1.size()];
                        for (int i = 0; i < points1.size(); i++) {
                            for (int k = 0; k < points1.size(); k++) {
                                ordinaryDistanceMatrix[i][k] = Double.MAX_VALUE;
                            }
                        }
                        String[][] ordinaryPointMatrix = new String[points1.size()][points1.size()];

                        for (int k = 0; k < points1.size(); k++) {
                            for (int m = 0; m < points1.size(); m++) {
                                //如果k和m相同就不用获取距离了，因为都是同一个点
                                if (k == m) {
                                    continue;
                                }

                                //获取当前循环里某两个点的距离，并存储到ordinaryDistanceMatrix和ordinaryPointMatrix
                                String origin = points1.get(k).getPoint()[0] + "," + points1.get(k).getPoint()[1];
                                String destination = points1.get(m).getPoint()[0] + "," + points1.get(m).getPoint()[1];
                                QueryWrapper<PointDistance> queryWrapper = new QueryWrapper<>();
                                queryWrapper.eq("origin", origin).eq("destination", destination).eq("is_delete", 0);
                                List<PointDistance> list = pointDistanceMapper.selectList(queryWrapper);
                                if (list.size() == 0) {
                                    double dis = saveDistanceInformation(points1.get(k), points1.get(m), transitDepotId, "ordinary", apiKey);
                                    ordinaryDistanceMatrix[k][m] = dis;
                                    ordinaryPointMatrix[k][m] = origin + ";" + destination;
                                } else {
                                    ordinaryDistanceMatrix[k][m] = Double.parseDouble(list.get(0).getDistance());
                                    ordinaryPointMatrix[k][m] = list.get(0).getOrigin() + ";" + list.get(0).getDestination();
                                }
                            }
                        }

                        //找当前小路线的起点和终点
                        int flag = 0;
                        for (int l = 1; l < basePath.size() - 1; l++) {
                            String[] split = basePath.get(l).split(",");
                            DoublePoint doublePoint = new DoublePoint(new double[]{Double.parseDouble(split[0]), Double.parseDouble(split[1])});
                            if (points1.contains(doublePoint)) {
                                flag = l;
                                break;
                            }
                        }

                        int start = 0;
                        int end = 0;
                        String target = basePath.get(flag) + ";" + basePath.get(flag + 1);
                        for (int s = 0; s < ordinaryPointMatrix.length; s++) {
                            boolean ifBreak = false;
                            String[] ordinaryPointMatrix1 = ordinaryPointMatrix[s];
                            for (int e = 0; e < ordinaryPointMatrix1.length; e++) {
                                if (ordinaryPointMatrix1[e] == null) {
                                    continue;
                                }

                                if (ordinaryPointMatrix1[e].equals(target)) {
                                    start = s;
                                    end = e;
                                    ifBreak = true;
                                    break;
                                }
                            }

                            //找到了就提早退出
                            if (ifBreak) {
                                break;
                            }
                        }

                        //计算当前循环的小路线
                        //在计算之前先判断是否存在，比如target=114.369658,25.275796;114.369658,25.275796的这种情况
                        //如果存在，那就是起点和终点一样的情况
                        List<Integer> tPath = new ArrayList<>();
                        if (start == 0 && end == 0) {
                            //找出这种情况的起点
                            int thisStart = 0;
                            for (int d = 0; d < points1.size(); d++) {
                                if ((points1.get(d).getPoint()[0] + "," + points1.get(d).getPoint()[1]).equals(basePath.get(flag))) {
                                    thisStart = d;
                                }
                            }
                            //计算这种特殊情况的小路线的最短路径
                            double dist = Double.MAX_VALUE;
                            for (int iii = 0; iii < points1.size(); iii++) {
                                if (iii == thisStart) {
                                    continue;
                                }
                                List<Integer> temp = calculatePartialPath(ordinaryDistanceMatrix, thisStart, iii);
                                double dis = totalDistance(temp, ordinaryDistanceMatrix);
                                //再加上最后一个点到中转站的距离,centroidClusters1.size()表示中转站的索引
                                dis += ordinaryDistanceMatrix[temp.get(temp.size() - 1)][thisStart];

                                if (dis < dist) {
                                    dist = dis;
                                    temp.add(thisStart);
                                    tPath = temp;
                                }
                            }
                        } else {
                            tPath = calculatePartialPath(ordinaryDistanceMatrix, start, end);
                        }
                        v1 += totalDistance(tPath, ordinaryDistanceMatrix);

                        if (tPath.size() == 2) {
                            continue;
                        }
                        //转换格式
                        StringBuilder stringBuilder = new StringBuilder();
                        for (int k = 0; k < tPath.size() - 1; k++) {
                            if (k == tPath.size() - 1 - 1) {
//                        String twoPoint = ordinaryPointMatrix[tPath.get(k - 1)][tPath.get(k)];
                                String twoPoint = ordinaryPointMatrix[tPath.get(k)][tPath.get(k + 1)];
                                String[] split = twoPoint.split(";");
                                stringBuilder.append(split[0]);
                            } else {
                                String twoPoint = ordinaryPointMatrix[tPath.get(k)][tPath.get(k + 1)];
                                String[] split = twoPoint.split(";");
                                stringBuilder.append(split[1]);
                                stringBuilder.append(";");
                            }
                        }

                        //加入到最终路径里
                        for (int l1 = 1; l1 < finalPath.size() - 1; l1++) {
                            String[] split2 = finalPath.get(l1).split(";");
                            if (split2.length > 1) {
                                continue;
                            }
                            String[] s = finalPath.get(l1).split(",");
                            DoublePoint doublePoint = new DoublePoint(new double[]{Double.parseDouble(s[0]), Double.parseDouble(s[1])});
                            if (points1.contains(doublePoint)) {
                                flag = l1;
                                break;
                            }
                        }
                        finalPath.add(flag + 1, stringBuilder.toString());
                    }

                }


                //存最终路线和对应的距离
                result.put(finalPath, v + v1);
            }


        }

        return result;
    }

    /**
     * 计算当前小路线和中转站的距离
     */
    private void calculateBridgeWithTransitDepot(Long transitDepotId, double[] transitDepot, int ceilK, double[][] bridgeDistanceMatrix, int ii, List<DoublePoint> points1, Object[][] bridgePointsMatrix, String apiKey) {
        double dist2 = Double.MAX_VALUE;
        DoublePoint origin2 = null;
        for (DoublePoint d1 : points1) {
            double v = calculateEuclideanDistance(d1.getPoint(), transitDepot);
            if (v < dist2) {
                dist2 = v;
                origin2 = d1;
            }
        }

        QueryWrapper<PointDistance> p1 = new QueryWrapper<>();
        p1.eq("origin", origin2.getPoint()[0] + "," + origin2.getPoint()[1]).eq("destination", transitDepot[0] + "," + transitDepot[1]).eq("is_delete", 0);
        List<PointDistance> l1 = pointDistanceMapper.selectList(p1);
        double distance3 = 0;
        if (l1.size() == 0) {
            distance3 = saveDistanceInformation(origin2, new DoublePoint(transitDepot), transitDepotId, "bridge", apiKey);
        } else {
            PointDistance pointDistance = l1.get(0);
            distance3 = Double.parseDouble(pointDistance.getDistance());
        }

        QueryWrapper<PointDistance> p2 = new QueryWrapper<>();
        p2.eq("origin", transitDepot[0] + "," + transitDepot[1]).eq("destination", origin2.getPoint()[0] + "," + origin2.getPoint()[1]).eq("is_delete", 0);
        List<PointDistance> l2 = pointDistanceMapper.selectList(p2);
        double distance4 = 0;
        if (l2.size() == 0) {
            distance4 = saveDistanceInformation(new DoublePoint(transitDepot), origin2, transitDepotId, "bridge", apiKey);
        } else {
            PointDistance pointDistance = l2.get(0);
            distance4 = Double.parseDouble(pointDistance.getDistance());
        }

        bridgeDistanceMatrix[ii][ceilK] = distance3;
        bridgeDistanceMatrix[ceilK][ii] = distance4;
        bridgePointsMatrix[ii][ceilK] = (origin2.getPoint()[0] + "," + origin2.getPoint()[1]) + ";" + (transitDepot[0] + "," + transitDepot[1]);
//        bridgePointsMatrix[ceilK][ii] = new DoublePoint(transitDepot) + ";" + origin2;
        bridgePointsMatrix[ceilK][ii] = (transitDepot[0] + "," + transitDepot[1]) + ";" + (origin2.getPoint()[0] + "," + origin2.getPoint()[1]);

    }

    /**
     * 计算路径的总长度
     */
    public static double totalDistance(List<Integer> path, double[][] graph) {
        double total = 0;
        for (int i = 0; i < path.size() - 1; i++) {
            total += graph[path.get(i)][path.get(i + 1)];
        }
        return total;
    }

    /**
     * 递归生成所有可能的路径
     */
    public static void generatePaths(List<Integer> path, List<List<Integer>> allPaths, double[][] graph, int start, int end) {
        if (path.size() == graph.length) {
            allPaths.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < graph.length; i++) {
            if (!path.contains(i)) {
                path.add(i);
                generatePaths(path, allPaths, graph, start, end);
                path.remove(path.size() - 1);
            }
        }
    }

    /**
     * 计算小路线
     */
    public List<Integer> calculatePartialPath(double[][] graph, int startPoint, int endPoint) {
        List<List<Integer>> allPaths = new ArrayList<>();
        generatePaths(new ArrayList<>(), allPaths, graph, startPoint, endPoint);

        List<Integer> shortestPath = null;
        double shortestLength = Double.MAX_VALUE;

        for (List<Integer> path : allPaths) {
            if (path.get(0) == startPoint && path.get(path.size() - 1) == endPoint) {
                double totalLen = totalDistance(path, graph);
                if (totalLen < shortestLength) {
                    shortestLength = totalLen;
                    shortestPath = new ArrayList<>(path);
                }
            }
        }

//        System.out.println("最短路径: " + shortestPath);
//        System.out.println("路径长度: " + shortestLength);
//        List<Integer> result = new ArrayList<>();
//        result.add(shortestPath);
//        result.add(shortestLength);
        return shortestPath;
    }

    /**
     * 获取两点的实际路线信息
     */
    public double saveDistanceInformation(DoublePoint point1, DoublePoint point2, Long transitDepotId, String type, String apiKey) {
        String url = "https://restapi.amap.com/v3/direction/driving";
//        String apiKey = "3acb45c690a8aed5095eff50887689f6";
        // 拼接经度和纬度字符串
        String origin = point1.getPoint()[0] + "," + point1.getPoint()[1];
        String destination = point2.getPoint()[0] + "," + point2.getPoint()[1];

        // 构建请求URL
        String requestUrl = url + "?origin=" + origin + "&destination=" + destination + "&number=FD08088&extensions=all&output=json&key=" + apiKey;

        double dist = 0.0;

        try {
            // 发送HTTP请求
            URL urlObj = new URL(requestUrl);
            HttpURLConnection connection = (HttpURLConnection) urlObj.openConnection();
            connection.setRequestMethod("GET");

            // 读取响应数据
            Scanner scanner = new Scanner(connection.getInputStream());
            StringBuilder response = new StringBuilder();
            while (scanner.hasNextLine()) {
                response.append(scanner.nextLine());
            }
            scanner.close();

            // 解析响应JSON数据
            ObjectMapper objectMapper = new ObjectMapper();
            JsonNode rootNode = objectMapper.readTree(response.toString());

//            double dist = rootNode.path("route").path("paths").get(0).path("distance").asDouble();
            JsonNode pathsNode = rootNode.path("route").path("paths");
            dist = pathsNode.get(0).path("distance").asDouble();
            StringBuilder polyline = new StringBuilder("");
            for (int i = 0; i < pathsNode.size(); i++) {
                JsonNode pathNode = pathsNode.get(i);
                String s = pathNode.path("steps").get(0).path("polyline").asText();
                if (i == 0 || i == pathsNode.size() - 1) {
                    polyline.append(s);
                } else {
                    polyline.append(";");
                    polyline.append(s);
                }
            }

            PointDistance pointDistance = new PointDistance();
            pointDistance.setDistance(String.valueOf(dist));
            pointDistance.setOrigin(origin);
            pointDistance.setDestination(destination);
            pointDistance.setPolyline(polyline.toString());
            pointDistance.setTransitDepotId(transitDepotId);
            pointDistance.setType(type);
            pointDistanceMapper.insert(pointDistance);

        } catch (IOException e) {
            e.printStackTrace();
        }

        return dist;
    }

    /**
     * 根据beskK值进行聚类，得到bestClusters聚类结果
     */
    private List<CentroidCluster<DoublePoint>> myKmeans(int bestK, int maxIterations, int randomSeed, ArrayList<DoublePoint> lngLatMatrix) {
        RandomGenerator randomGenerator = new MersenneTwister(randomSeed);
        //使用k-means聚类算法进行分类，聚类的簇数为best_k
        KMeansPlusPlusClusterer<DoublePoint> bestClusterer = new KMeansPlusPlusClusterer<>(bestK, maxIterations, new EuclideanDistance(), randomGenerator);
        return bestClusterer.cluster(lngLatMatrix);
    }

    /**
     * 两点之间欧氏距离的计算方法
     */
    private double calculateEuclideanDistance(double[] point1, double[] point2) {
        double sum = 0.0;
        for (int i = 0; i < point1.length; i++) {
            sum += Math.pow(point1[i] - point2[i], 2);
        }
        return Math.sqrt(sum);
    }

}
